//
//  Problem206.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/9.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 206. 反转链表
 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 示例 1：
     输入：head = [1,2,3,4,5]
     输出：[5,4,3,2,1]
 示例 2：
     输入：head = [1,2]
     输出：[2,1]
 示例 3：
     输入：head = []
     输出：[]
  
 提示：
     链表中节点的数目范围是 [0, 5000]
     -5000 <= Node.val <= 5000
     进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 */
@objcMembers class Problem206: NSObject {
    func solution() {
        let root = ListNode(1)
        root.next = ListNode(2)
        root.next?.next = ListNode(3)
        root.next?.next?.next = ListNode(4)
        root.next?.next?.next?.next = ListNode(5)
        print(reverseList(root))
    }
    
    /*
     递归
     */
    func reverseListDi(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        let node = reverseListDi(head?.next)
        head?.next?.next = head
        head?.next = nil
        return node
    }
    
    /*
     迭代
     */
    func reverseList(_ head: ListNode?) -> ListNode? {
        var pre: ListNode? = nil
        var node = head
        while node != nil {
            let next = node?.next
            node?.next = pre
            pre  = node
            node = next
        }
        return pre
    }
}
